package com.ljy.my_study.leetcode.最大连续1的个数III;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author lijunying
 * @date 2021/2/19 9:25
 */
public class TestMain {

//    给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
//
//    返回仅包含 1 的最长（连续）子数组的长度。
//
//             
//
//    示例 1：
//
//    输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
//    输出：6
//    解释：
//            [1,1,1,0,0,1,1,1,1,1,1]
//    粗体数字从 0 翻转到 1，最长的子数组长度为 6。
//    示例 2：
//
//    输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
//    输出：10
//    解释：
//            [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
//    粗体数字从 0 翻转到 1，最长的子数组长度为 10。
//             
//
//    提示：
//
//            1 <= A.length <= 20000
//            0 <= K <= A.length
//    A[i] 为 0 或 1 
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/max-consecutive-ones-iii
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        int[] A=new int[]{1,1,1,0,0,0,1,1,1,1,0};
        int K=2;
        System.out.println(new TestMain().longestOnes(A,K));
        A=new int[]{0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};
        K=3;
        System.out.println(new TestMain().longestOnes(A,K));
        A=new int[]{1,0,0,1,1,0,0,0,1};
        K=3;
        System.out.println(new TestMain().longestOnes(A,K));

        A=new int[]{0,1,1,0,0,0,1,1,1,0};
        K=0;
        System.out.println(new TestMain().longestOnes(A,K));
        A=new int[]{0,0,1,1,1,0,1};
        K=0;
        System.out.println(new TestMain().longestOnes(A,K));
        A=new int[]{1,1,1,0,0,0,1,1,1,1,0};
        K=2;
        System.out.println(new TestMain().longestOnes(A,K));
    }

    public int longestOnes(int[] A, int K) {

        int len=A.length;
        int max=0;
        int count=0;
        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<len;i++){
            if(A[i]==0){
                queue.offer(i);
                if(queue.size()<=K){
                    count++;
                }else{
                    max=Math.max(max,count);
                    count=i-queue.poll();
                }
            }else{
                count++;
            }
        }
        max=Math.max(max,count);
        return max;
    }
}
